package com.fwpsl.graph.shortestpath.multisource;

import com.fwpsl.graph.Edge;
import com.fwpsl.graph.Graph;
import com.fwpsl.graph.Vertex;

import java.util.*;

import static com.fwpsl.graph.shortestpath.multisource.AbstractMultiSource.Node.PATH_NODE_TYPE_SINGLE;

/**
 * @author: 风戏fw
 * @date: 2024/4/1
 * @description: Floyd-Warshall(弗洛伊德)算法可以找到图中所有节点对之间的最短路径。
 * 注意事项：
 * Floyd-Warshall算法可以处理负权重的边，但不能处理负权重的环。如果存在负权重的环，则最短路径问题可能是没有定义的，
 * 因为可以通过多次遍历环来得到任意小的路径长度。在实际应用中，需要确保图中没有负权重的环。
 */
public class FloydWarshall<T> extends AbstractMultiSource<T> {
    private static final int INF = Integer.MAX_VALUE;

    /**
     * 最短路径（单条）
     */
    @Override
    public Node[][] singlePathList(Graph<T> graph) {
        List<Vertex<T>> vertexList = new ArrayList<>(graph.getVertices());
        int vNum = vertexList.size();

        // nodeArr表示图的邻接矩阵。初始时，如果两个节点之间没有直接的边，我们将其值设置为 `Integer.MAX_VALUE`，表示无穷大。
        // 对于带权重的图，将权重直接放在相应的位置上。
        Node[][] nodeArr = getNodeArr(vertexList, 1);

        // Floyd-Warshall算法通过三层循环，依次考虑所有节点作为中间点，更新任意两点之间的最短路径。
        // 如果通过中间点 `k` 可以找到更短的路径，就更新 `nodeArr[i][j]`。
        for (int k = 0; k < vNum; k++) {
            for (int i = 0; i < vNum; i++) {
                for (int j = 0; j < vNum; j++) {
                    if (nodeArr[i][k].distance == INF || nodeArr[k][j].distance == INF) {
                        continue;
                    }

                    if (nodeArr[i][k].distance + nodeArr[k][j].distance < nodeArr[i][j].distance) {
                        nodeArr[i][j].distance = nodeArr[i][k].distance + nodeArr[k][j].distance;
                        nodeArr[i][j].preVertex = vertexList.get(k);
                    }
                }
            }
        }

        return nodeArr;
    }

    /**
     * 最短路径（单条）
     */
    public Node[][] singlePathList(List<Vertex<T>> vertexList, Node[][] nodeArr) {
        int vNum = vertexList.size();

        for (int i = 0; i < vNum; i++) {
            Vertex<T> startVertex = vertexList.get(i);
            for (int j = 0; j < vNum; j++) {
                // 假设图中没有自环（即没有节点到其自身的边），如果有自环且权重为正，则需要在初始化时将nodeArr[i][i]设置为 0。
                // 如果自环的权重为其他值，则需要根据具体情况进行调整。
                nodeArr[i][j] = new Node(startVertex, vertexList.get(j), (i == j ? 0 : INF), PATH_NODE_TYPE_SINGLE);
            }

            for (Edge<T> edge : startVertex.getEdges()) {
                int j = vertexList.indexOf(edge.getDestination());
                nodeArr[i][j].distance = (int) edge.getWeight();
            }
        }

        // Floyd-Warshall算法通过三层循环，依次考虑所有节点作为中间点，更新任意两点之间的最短路径。
        // 如果通过中间点 `k` 可以找到更短的路径，就更新 `nodeArr[i][j]`。
        for (int k = 0; k < vNum; k++) {
            for (int i = 0; i < vNum; i++) {
                for (int j = 0; j < vNum; j++) {
                    if (nodeArr[i][k].distance == INF || nodeArr[k][j].distance == INF) {
                        continue;
                    }

                    if (nodeArr[i][k].distance + nodeArr[k][j].distance < nodeArr[i][j].distance) {
                        nodeArr[i][j].distance = nodeArr[i][k].distance + nodeArr[k][j].distance;
                        nodeArr[i][j].preVertex = vertexList.get(k);
                    }
                }
            }
        }

        return nodeArr;
    }

    /**
     * 最短路径（多条）
     */
    @Override
    public Node[][] multiPathList(Graph<T> graph) {
        List<Vertex<T>> vertexList = new ArrayList<>(graph.getVertices());
        int vNum = vertexList.size();

        // nodeArr表示图的邻接矩阵。初始时，如果两个节点之间没有直接的边，我们将其值设置为 `Integer.MAX_VALUE`，表示无穷大。
        // 对于带权重的图，将权重直接放在相应的位置上。
        Node[][] nodeArr = getNodeArr(vertexList, 2);

        // Floyd-Warshall算法通过三层循环，依次考虑所有节点作为中间点，更新任意两点之间的最短路径。
        // 如果通过中间点 `k` 可以找到更短的路径，就更新 `nodeArr[i][j]`。
        for (int k = 0; k < vNum; k++) {
            for (int i = 0; i < vNum; i++) {
                for (int j = 0; j < vNum; j++) {
                    if (nodeArr[i][k].distance == INF || nodeArr[k][j].distance == INF) {
                        continue;
                    }

                    if (nodeArr[i][k].distance + nodeArr[k][j].distance < nodeArr[i][j].distance) {
                        nodeArr[i][j].distance = nodeArr[i][k].distance + nodeArr[k][j].distance;
                        nodeArr[i][j].preVertexSet = new HashSet<>();
                        nodeArr[i][j].preVertexSet.add(vertexList.get(k));
                    } else if (nodeArr[i][k].distance + nodeArr[k][j].distance == nodeArr[i][j].distance
                            && nodeArr[i][j].distance > 0 && i != k && j != k) {
                        nodeArr[i][j].preVertexSet.add(vertexList.get(k));
                    }
                }
            }
        }

        return nodeArr;
    }

    public static void main(String[] args) {
        // 节点： 1 - 6
        // 邻接矩阵
        int[][] graphArr = {
                {0, 2, 3, 6, 0, 0},
                {2, 0, 0, 0, 4, 6},
                {3, 0, 0, 2, 0, 0},
                {6, 0, 2, 0, 1, 3},
                {0, 4, 0, 1, 0, 0},
                {0, 6, 0, 3, 0, 0}
        };
        Graph<Integer> graph = Graph.buildIntGraph(graphArr);

        FloydWarshall<Integer> fw = new FloydWarshall<>();

        // 最短路径（单条）
        fw.testSinglePathList(graph);

        System.out.println();

        // 最短路径（多条）
        fw.testMultiPathList(graph);
    }
}